////
//
/// \file ./include/inc/parser/source_buffer.hpp
//
//  Copyright 2008 Chandler Carruth
//
//  Licensed under the Apache License, Version 2.0 (the "License"); you may not
//  use this file except in compliance with the License.  You may obtain a copy
//  of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
//  WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.  See the
//  License for the specific language governing permissions and limitations
//  under the License.
//
////

#ifndef     inc_parser_source_buffer_header_
#define     inc_parser_source_buffer_header_

#include <stdint.h>

#include <deque>
#include <string>

#include <boost/iterator/iterator_facade.hpp>
#include <boost/regex.hpp>
#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>

namespace inc {
namespace parser {

/// \brief Source code buffer
/// \author Chandler Carruth
/// \date 2008.10.13
///
/// This class represents a buffer of source code, and various operations and
/// transformations which can be done upon it. It includes significant logic to
/// manage buffering of the data so that slow I/O sources can be optimized down
/// the road.

class SourceBuffer {
public:
  /// This is the fundamental type used for indexing into the source buffer.
  /// This needs to remain a signed type in order to reserve the high bit for
  /// expressing differences between two indices.
  typedef int64_t IndexType;

  /// This is the fundamental element type for the source code. We represent
  /// things as bytes in order to avoid the overhead of interpreting UTF8
  /// encoded data. Thus, we have a fixed-size unit, and that simply may or may
  /// not refer to an individual character.
  typedef uint8_t DataType;

  /// This provides the iterator concept over the source code. The buffer is
  /// not cyclic, and moves forward, so we always know where to start, but may
  /// not know where the "end" of the source is. This leads to an offset-based
  /// iterator into the source, with the "end" being a special pre-defined
  /// value similar to "npos" in the standard string implementation. This class
  /// is templated purely to allow defining both constant and mutable
  /// iterators.
  template< typename BufferT, typename DataT = typename BufferT::DataType >
  class BasicIterator
      : public boost::iterator_facade<
          BasicIterator< BufferT, DataT >,
          DataT,
          boost::random_access_traversal_tag,
          DataT&,
          IndexType
        >
  {
  private:
    // This is black magic used by the enable_if<> stuff in the conversion
    // constructor below.
    struct enabler {};

    // Facilitate referencing self and template-dependent base members.
    typedef BasicIterator< BufferT, DataT > SelfT;

  public:
    BasicIterator()
        : buffer( NULL ), i( 0 )
    {}

    /// The simplest constructor requires a reference to a buffer object be
    /// specified. The index defaults to zero, the beginning, and can be
    /// specified if desired.
    explicit BasicIterator( BufferT* buffer_, IndexType i_ = 0 )
        : buffer( buffer_ ), i( i_ )
    {
      assert( buffer != NULL );
    }

    /// This template provides both the standard copy constructor, and
    /// conversion constructors for interoperable iterators. The enable_if<>
    /// magic prevents the constructor from being instantiated for the constant
    /// -> mutable transition, clarifying compiler error messages.
    template< typename OtherBufferT, typename OtherDataT >
    BasicIterator( const BasicIterator< OtherBufferT, OtherDataT >& other,
                   typename boost::enable_if<
                       boost::is_convertible< OtherBufferT*, BufferT* >,
                       enabler
                   >::type = enabler() )
        : buffer( other.buffer ), i( other.i )
    {}

    /// This matches a provided string in the source buffer beginning at this
    /// position, and steps the iterator past it if it matches. It returns true
    /// upon a successful match.
    bool
    match_str( const std::string& text )
    {
      return buffer->match_str( text, *this, *this );
    }

    /// This matches a provided string in the source buffer beginning at this
    /// position, and stores the end of the match into the provided parameter.
    /// It returns true upon a successful match. The end position is *always*
    /// set, and is equal to this in the event of no match. The provided
    /// parameter must not have the same address as this iterator; the above
    /// form is provided for that behavior.
    bool
    match_str( const std::string& text, SelfT& end_pos ) const
    {
      assert( this != &end_pos );
      return buffer->match_str( text, *this, end_pos );
    }

    /// This matches a provided regular expression within the source buffer
    /// beginning at this position, and steps the iterator past any match.  It
    /// returns true upon a successful match.
    bool
    match_re( const boost::regex& re )
    {
      return buffer->match_re( re, *this, *this );
    }

    /// This matches a provided regular expression within the source buffer
    /// beginning at this position, and stores the ending position of the match
    /// into the provided parameter. It returns true upon a successful match.
    /// The end position is *always* set, and is equal to this in the event of
    /// no match. The provided parameter must not have the same address as this
    /// iterator; the above form is provided for that behavior.
    bool
    match_str( const boost::regex& re, SelfT& end_pos ) const
    {
      assert( this != &end_pos );
      return buffer->match_re( re, *this, end_pos );
    }

  private:
    // This is the class that actually accesses our private API.
    friend class boost::iterator_core_access;

    // Interoperability between various specialization requires private access.
    template< typename, typename > friend class BasicIterator;

    typename SelfT::reference dereference() const { return (*buffer)[i]; }

    template< typename OtherBufferT, typename OtherDataT >
    bool
    equal( const BasicIterator< OtherBufferT, OtherDataT >& it ) const
    {
      return buffer == it.buffer && i == it.i;
    }

    void
    advance( typename SelfT::difference_type n )
    {
      i = buffer->advance_index( i, n );
    }

    void increment() { advance( 1 ); }
    void decrement() { advance( -1 ); }

    template< typename OtherBufferT, typename OtherDataT >
    typename SelfT::difference_type
    distance_to( const BasicIterator< OtherBufferT, OtherDataT >& it ) const
    {
      assert( buffer == it.buffer );
      assert( i <= it.i );
      return it.i - i;
    }

    // This is a reference to the indexed source buffer. TODO(chandlerc):
    // I hate this; iterators are often passed and stored as pairs, and
    // embedding the handle to the source buffer within the iterator is
    // wasteful, but there is no convenient way to allow dereferencing to be
    // parameterized.
    BufferT* buffer;

    // This is an index into the source buffer.
    IndexType i;
  };

  // Typedefs for the const and regular iterators.
  typedef BasicIterator< SourceBuffer, DataType > Iterator;
  typedef BasicIterator< const SourceBuffer, const DataType > ConstIterator;

  /// The most basic constructor provides the entire sequence of data upfront,
  /// and takes advantage of none of the advanced scalability built into the
  /// API. That said, it's the most important for early development, as all
  /// others are optimizations.
  explicit SourceBuffer( const std::string& data_ );

  /// This class is virtual purely so that it's clients can be tested via
  /// dependency injection. This is a potential source of performance overhead,
  /// and benchmarks may dictate changing this later.
  virtual ~SourceBuffer() {};

  /// Non-constant lookup into the buffer.
  DataType& operator[]( IndexType i ) { return data[i]; }

  /// Constant lookup into the buffer.
  const DataType& operator[]( IndexType i ) const { return data[i]; }

  Iterator begin() { return Iterator( this ); }
  ConstIterator begin() const { return ConstIterator( this ); }

  Iterator end() { return Iterator( this, -1 ); }
  ConstIterator end() const { return ConstIterator( this, -1 ); }

  /// Match a fixed string within the source code at a particular position.
  /// Note that the input iterator is passed by value, and thus its address may
  /// also be passed in as the iterator to receive the end position. The end
  /// position is *always* set, and equals the input position if no match was
  /// found.
  virtual bool match_str( const std::string& text,
                          Iterator pos,
                          Iterator& end_pos );

  /// Match a regular expression within the source code, starting at a specific
  /// position. The input iterator is passed by value to allow the same
  /// variable's address to be passed as the end position of the match.
  virtual bool match_re( const boost::regex& re,
                         Iterator pos,
                         Iterator& end_pos );

private:
  // Helper method to allow the buffer to perform the advance of Iterator's
  // indices. Dropping to the buffer for these operations enables lazily
  // pulling data and avoids pre-computing the size for "end" iterators.
  IndexType
  advance_index( IndexType i, IndexType dist ) const
  {
    i += dist;
    if( i >= data.size() )
      i = -1;

    return i;
  }

  // The underlying data store is an STL deque. This structure should provide
  // *very* efficient indexing and tail-growth, but may require a custom
  // implementation due to poor STL implementations or data optimizations for
  // the match_* methods.
  std::deque< DataType > data;
};

} // end parser namespace
} // end inc namespace
#endif  //  inc_parser_source_buffer_header_
